package array.binarySearch;

/**
 * 题目: 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
        如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

 *数组中插入目标值的四种情况:目标值在所有元素前，目标值在所有元素后，
                        目标值插入数组中的位置，目标值等于数组中的某个元素

 *两种方法: 暴力法，二分法
 */

/**
 * 暴力法
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
public class searchInsertLocation {
    public static int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length ; i++) {
            //处理一下三种情况:目标值在数组所有元素前等于数组中某一个元素，目标值插入数组中的位置
            if(nums[i]>=target){
                return i;
            }
        }
        return nums.length;
    }
}*/

//二分法
public class searchInsertLocation {
public int searchInsert(int[] nums, int target) {
    int left = 0;
    int right =nums.length-1;

    //当数组中存在目标元素
    while(left<=right){
        int mid = (left+right)/2;
        if(nums[mid]>target){
            right=mid-1;
        }
        else if(nums[mid]<target){
            left=mid+1;
        }
        else{
            return mid;
        }
    }

    // 分别处理如下三种情况
    // 目标值在数组所有元素之前  [0, -1]
    // 目标值插入数组中的位置 [left, right]，return  right + 1
    // 目标值在数组所有元素之后的情况 [left, right]， 因为是右闭区间，所以 return right + 1
    return right+1;
}}




